import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 递归：从哪里进从哪里出，原来返回，在方法中又开启一个调用方法
 */
public class TreeTraverse {
    public static void main(String[] args) {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        Node G = new Node("G");
        Node H = new Node("H");
        Node I = new Node("I");
        Node J = new Node("J");
        Node K = new Node("K");

        A.setLeft(B);
        A.setRight(C);

        B.setLeft(D);
        B.setRight(E);

        D.setLeft(G);
        E.setLeft(H);
        E.setRight(I);

        C.setRight(F);
        F.setLeft(J);
        F.setRight(K);
        print1(A);
        System.out.println();
        print2(A);
        System.out.println();
        print3(A);
        System.out.println();
        print4(A);
        System.out.println("(递归)树的深度："+deep(A));

    }


    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public static class Node{
        private Object value;
        private Node left;
        private Node right;

        public Node(Object value){
            this.value = value;
        }
    }

    /**
     * 先序遍历
     * 递归：1、终止条件：出口
     *      2、递归体
     * @param node 根节点
     */
    public static void print1(Node node){

        if(null == node){
            return;
        }

        System.out.print(node.getValue());
        print1(node.getLeft());
        print1(node.getRight());
    }

    /**
     * 中序遍历
     * 递归：1、终止条件：出口
     *      2、递归体
     * @param node 根节点
     */
    public static void print2(Node node){

        if(null == node){
            return;
        }

        print2(node.getLeft());
        System.out.print(node.getValue());
        print2(node.getRight());
    }

    /**
     * 后序遍历
     * 递归：1、终止条件：出口
     *      2、递归体
     * @param node 根节点
     */
    public static void print3(Node node){

        if(null == node){
            return;
        }

        print3(node.getLeft());
        print3(node.getRight());
        System.out.print(node.getValue());
    }

    /**
     * 层序遍历
     */
    public static void print4(Node node){
        Queue<Node> queue = new LinkedList<>();

        //如果根结点不为空，则将第一层结点放入队列
        if(null != node){
            queue.offer(node);
        }
        int deep = 0;
        //当队列不为空 执行循环
        while(!queue.isEmpty()){
            //记录此时队列的长度，此时的num代表某一层一共有多少个结点，防止被后面入队的结点个数影响输出这一层的结点
            int num = queue.size();

            //对每一层的结点进行遍历（从左到右）
            for (int i = 0; i < num; i++) {
                //取出这一层 第一个结点
                Node topNode = queue.poll();
                System.out.print(topNode.getValue());

                if(topNode.left != null){
                    queue.offer(topNode.left);
                }

                if(topNode.right != null){
                    queue.offer(topNode.right);
                }

            }
            deep++;
            System.out.print("  =====个数："+num);
            System.out.println();
        }
        System.out.println("(非递归)树的深度为："+deep);

    }

    /**
     * 递归求树的深度
     * @param root
     */
    public static int deep(Node root){
        return root == null ? 0 : Math.max(deep(root.left), deep(root.right)) + 1;

    }

}
